The field of the invention is that of the transmission or broadcasting of digital data signals. More specifically, the invention relates to the decoding of transmitted digital signals and, especially, source decoding. More specifically again, the invention can be applied to the decoding of data encoded with a source encoding method using entropic codes such as the VLC or variable length code.
The digital communications systems commonly used today rely on encoding systems that implement, on the one hand, source encoding and, on the other, channel encoding. Conventionally, these two encoding systems are optimized separately. The purpose of the source encoding is to achieve maximum reduction in the redundancy of the source signal to be transmitted. Then, to protect this information from the disturbance inherent in all transmission, the channel encoder introduces controlled redundancy.
At present, the best results in source (audio, image and/or video source) encoding are obtained by using discrete cosine transform (DCT) or wavelets commonly associated with VLCs. Channel encoding conventionally implements turbo-codes [1] (the bibliographical references are assembled in appendix C in order to facilitate the reading of the present description), and more generally that of the soft-decision iterative decoders. These techniques have permitted decisive progress towards the theoretical limit defined by Shannon [2].
However, the optimality of the separation between source encoding and channel encoding is guaranteed only for codes with a length tending towards infinity. Consequently, research has also been conducted to obtain, along with finite-length channel codes, joint source-channel encoding and/or decoding systems.
The invention thus relates to the decoding of entropic codes, and especially but not exclusively to the joint source-channel decoding of a system implementing an entropic code.
Combined decoding has many fields of application, for example video image transmission, especially according to the MPEG 4 (Moving Picture Expert Group) standard.
Variable length codes are well known. For example, appendix A gives a quick review of the Huffman code. The special embodiment of the invention described hereinafter can be applied especially but not exclusively to this type of entropic code.
Variable length codes are of vital importance in the limitation of the band occupied by the transmitted signal, but their use makes transmission less error-robust. Furthermore, it is difficult to use the a priori probabilities of the source when decoding, because it is not possible to know the beginning and the end of each word, since the length of these words is, by definition, variable.
A variety of techniques has been proposed for joint source-channel decoding related to the use of these variable length codes. In particular:
K. Sayood and N. Demir have proposed [4] a decoding of VLC words. The two major drawbacks of this type of decoding are found here. These are lattice complexity that increases rapidly with the number of different VLC words and decoding that remains at the symbol (or word) level;
Ahshun H. Murad and Thomas E. Fuja [5] propose a super-lattice method in which the decoding lattice is the one obtained by the product of the lattice of the channel decoder, the lattice of the source decoder and the lattice representing the source. This approach is clearly limited by the complexity of the decoding;
K. P. Subbalaskshmi and J. Vaisey [6] give a lattice structure that can be used to know the beginning and end of each word and therefore enables the use of the a priori information available on the VLC words sent. This decoder works on the words and sends no extrinsic information on the decoded bits;
Jiangtao Wen and John D. Villasenor [7] use a decoding block working on the words and sending a reliability value for the decoded sequence. This decoder uses the number of VLC words in the received sequence as a priori information.
It is a goal of the invention especially to overcome the different drawbacks of these prior art techniques.
More specifically, it is a goal of the invention to provide a technique for the decoding of data encoded with an entropic code used to obtain a reduction in the symbol error rate, especially with respect to separate (tandem) decoding schemes.
On the implementation aspects, it is a goal of the invention to provide a decoding technique of this kind with very low complexity as compared with known techniques.
In particular, it is a goal of the invention to provide a decoding technique of this kind with a reasonable operational complexity, namely one that can be implemented in practice at reasonable cost, especially when the number of different words considered by the entropic code is high.
It is also a goal of the invention to provide a technique of this kind that delivers confidence bits that can be exploited in the channel decoding operation.
In other words, it is a particular goal of the invention to provide methods of joint source-channel decoding that are well suited to the entropic codes, especially the VLCs and the RVLCs.
Yet another goal of the invention is to provide a decoding technique of this kind that improves the performance obtained with known channel codes, especially encoders implementing turbo-codes.,
These goals as well as others that shall appear more clearly here below are achieved by means of a method for the decoding of received digital data, corresponding to sent digital data encoded by means of an entropic code associating a distinct sequence of bits with each of the words of an alphabet, the length of this sequence depending on the probability of occurrence of said word.
According to the invention, this method implements a decoding lattice for which each transition corresponds to a binary value 0 or 1 of one of the bits of a sequence of bits corresponding to one of said words.
In other words, the invention is based on a novel approach to the decoding of variable length codes, it is the transitions at bit level that are considered and not, conventionally, the transitions at the word level or the symbol level.
This approach is novel and non-obvious. Those skilled in the art are convinced that the fact that the symbols have variable length makes it necessary to work at the symbol level in order to know the beginning and end of the symbols. The inventors show that this is not obligatory.
Furthermore, the fact of working at the bit level gives a piece of information that can be exploited by a channel decoder and therefore enables joint decoding, as shall be seen more clearly here below.
Said entropic code may take the form of a binary tree comprising a root node, a plurality of intermediate nodes and a plurality of leaf nodes, a sequence of bits corresponding to one of said words being formed in considering the successive transitions of said tree from said root node up to the leaf node associated with said word. In this case, advantageously, the states of each stage of said lattice comprise a single state known as an extremal state, corresponding to said root node and to all of said leaf nodes, and a distinct state, called an intermediate state, for each of said intermediate nodes.
Thus, a simple lattice with a limited number of states is obtained.
Preferably, a piece of likelihood information is associated with each transition of said lattice. Said likelihood information is then advantageously a metric taking account, firstly of a piece of information representing the transmission channel and secondly a piece of a priori information on said entropic code.
For example, said a priori information belongs to the group comprising:
the entropic code implemented; and/or
the a priori probabilities of each of said words of the code; and/or
the number of words sent; and/or
borderline values for the coefficients.
Thus, the following probability can be computed for each of said transitions:
xcex93i[(xk,xkp),dk, dkxe2x88x921]=Pr(xk/ak=i)Pr(ykp/ak=i,dk,dkxe2x88x921)Pr{ak=i,dk/dkxe2x88x921}
for which the information and parameters are described here below.
Said entropic code may belong especially to the group comprising:
Huffman codes;
Reversible variable length codes (RVLC).
Preferably, in the case of an RVLC code, said a priori information is used for a forward phase in the path through said lattice and a backward phase in the path through said lattice.
The invention also relates to a method for the joint source-channel decoding of the digital signals received, based on this approach, where the source encoding implements an entropic code associating a distinct bit sequence with each of the words of an alphabet, the length of the sequence being a function of the probability of occurrences of said word.
According to the invention, this joint decoding method implements a source decoding operation using at least one decoding lattice, each transition of which corresponds to a binary value 0 or 1 of one of the bits of the bit sequence corresponding to one of said words, said source decoding operation delivering a piece of information extrinsic to the channel decoding.
The channel decoding may advantageously implement a turbo-code type of decoding that can rely on a parallel type implementation or a serial type approach.
Advantageously, the joint decoding method of the invention relies on an iterative implementation.
In this case, each of the iterations may sequentially comprise a channel decoding step and a source decoding step, said channel decoding step delivering a piece of channel information taken into account in said source decoding step, this source decoding step delivering an a priori piece of information taken into account in said channel decoding step.
In particular, the method may comprise:
a first channel decoding step;
a first source decoding step, fed by said first channel decoding step;
a second channel decoding step, fed by said first channel decoding step and said first source decoding step, through an interleaver identical to the interleaver implemented at the decoding, and feeding said first channel decoding step, through a de-interleaver symmetrical with said interleaver;
a second source decoding step fed by said second channel decoding step through said de-interleaver and feeding said first channel decoding step.
According to another aspect, the invention also relates to a method for the joint source-channel decoding of a received digital signal, where the source encoding operation implements an entropic code associating a distinct bit sequence with each of the words of an alphabet, the length of this bit sequence being a function of the probability of occurrence of said word, said method implementing a channel decoding lattice, similar to the channel encoding lattice, in which, with each state of each stage, there is associated a piece of information representing a sequence, passing through this state, of bits decoded from the past, with respect to the path direction of said lattice, designating the position of the bits considered in the tree representing said entropic code and/or a piece of information for the verification the number of decoded words and/or the value taken by said decoded bits.
In this case, the joint decoding method advantageously comprises, for each of said states, the following steps:
the addition, to the two branches coming into said state, of the channel metric and the source metric;
the comparison of the two new metrics obtained, and the selection of the shortest metric;
if said piece of information designating the position indicates the end of a word, considering the node to be a leaf of the tree, and, if not, passing on to the next node in the tree.
Preferably, this method implements an iterative procedure which may for example comprise the following steps:
a first channel decoding operation, implementing a channel decoding lattice for which each state has a piece of information available designating the position of the bits considered in the tree representing said entropic code;
a second channel decoding operation, fed by said first channel decoding, through an interleaver identical to the interleaver implemented at the decoding, and feeding said first channel decoding step, through a de-interleaver symmetrical with said interleaver;
a source decoding operation fed by said second channel decoding, through said de-interleaver.
Again, in this case, a (parallel or series) turbo-code type decoding is implemented.
Advantageously, each iteration of said turbo-code type decoding implements a block matrix, having rows and columns, on which a row decoding operation (or column decoding operation respectively) is performed followed by a column decoding operation (or row decoding operation respectively), and this a priori information is used for said row decoding operation (and column decoding operation respectively).
In this case, preferably, each row (or column respectively) corresponds to a code word formed by k information bits and n-k padding bits, and each piece of a priori information is used on said k information bits.
In particular, when the code used is an RVLC code, it is advantageous to concatenate the channel decoding and source decoding lattices, said channel decoding being controlled by a piece of a priori information on the source.
It is then possible to apply a parallel or series type of algorithm known as the xe2x80x9cList-Viterbixe2x80x9d algorithm, associated with a step for the replacement of a sequence not authorized by the source, by the most probable authorized sequence, on the path through the channel decoding lattice, or an algorithm known as a xe2x80x9cSUBMAPxe2x80x9d, in the directions of the forward and backward directions of the channel decoding lattice.
Preferably, the decoding method also implements a step to detect the end of the sequence of code words to be decoded.
This detection step may rely especially on the implementation of at least one of the techniques belonging to the group comprising:
the insertion at transmission of an end-of-sequence piece of information;
the insertion of padding bits, so that the lattice of the channel decoder associated with the sequence sent ends in a known state;
the use of the technique known as xe2x80x9ctail-bitingxe2x80x9d;
the use of a circular lattice.
Advantageously, in the different embodiments referred to here above, the method furthermore comprises a step of searching for the most probable authorized sequence by means of a reduced symbol lattice having a single initial state (d0) from which there are as many outgoing and arriving words as there are code words.
Naturally, the invention also relates to all the digital data decoding devices implementing one of the decoding methods described here above, as well as digital signal transmission systems implementing an entropic source encoding operation and a channel encoding operation at transmission and a decoding operation, as described further above, at reception.